package com.security.session;

public class ModularArithmeticUtils {
	
	public static long multiplicativeModularInverse(long b, long n)
	{
		long n0 = n;
		long t0 = 0;
		long t = 1;
		long q = n0 % b;
		long r = n0 - q * b;
		
		while(r > 0)
		{
			long temp = t0 - q * t;
			if (temp >= 0) 
				temp = temp % n;
			else
				temp = n - ((-temp) % n);
			
			t0 = t;
			t = temp;
			n0 = b;
			b = r;
			q = n0 / b;
			r = n0 - q * b;
		}
		
		if (b != 1) {
			return -1;
		}
			
		else {
			return t;
		}			
	}

}
